package com.yequan.leetcode.lrucache.LRUCache_146;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : Administrator
 * @date : 2020/6/17
 */
public class RecordLRUCache {

    /**
     * 存储内容的缓存
     */
    private Map<Integer, DBLinkedNode> cache;
    /**
     * 双向链表
     */
    private DBLinkedNode head, tail;
    private int capacity;
    private int size;

    public RecordLRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new DBLinkedNode();
        tail = new DBLinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    /**
     * 1.如果缓存中存在: 返回值, 将该值的节点移至链表第一个节点
     * 2.如果缓存中不存在: 返回-1
     *
     * @param key
     * @return
     */
    public int get(int key) {
        DBLinkedNode node = cache.get(key);
        if (null == node) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    /**
     * 新增值:
     * 1.如果缓存中存在该key: 更新值,并且将该值的节点移至第一个节点
     * 2.如果缓存中不存在该key:
     * a.空间足够:往cache中写该值,并将该值的节点存入链表的第一个节点
     * b.空间不够:删除链表和cache中最后一个值,,往cache中写该值,并将该值的节点移至链表的第一个节点
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        DBLinkedNode node = cache.get(key);
        if (null == node) {
            DBLinkedNode newNode = new DBLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            if (++size > capacity) {
                DBLinkedNode tailNode = removeTailNode();
                cache.remove(tailNode.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    /**
     * 删除尾部节点
     */
    private DBLinkedNode removeTailNode() {
        DBLinkedNode node = tail.pre;
        removeNode(node);
        return node;
    }

    /**
     * 将节点移动到第一个节点
     * 1.先删除该节点
     * 2.在头结点上新增
     *
     * @param node
     */
    private void moveToHead(DBLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 头结点新增
     *
     * @param node
     */
    private void addToHead(DBLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    /**
     * 移除节点
     *
     * @param node
     */
    private void removeNode(DBLinkedNode node) {
        DBLinkedNode pre = node.pre;
        DBLinkedNode next = node.next;
        pre.next = next;
        next.pre = pre;
    }

    private static class DBLinkedNode {
        DBLinkedNode pre;
        DBLinkedNode next;
        int key;
        int value;

        public DBLinkedNode() {
        }

        public DBLinkedNode(int value) {
            this.value = value;
        }

        public DBLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}
